{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Largest Number After Digit Swaps by Parity"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #sorting #heap-priority-queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #排序 #堆（优先队列）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: largestInteger"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #按奇偶性交换后的最大数字"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个正整数 <code>num</code> 。你可以交换 <code>num</code> 中 <strong>奇偶性</strong> 相同的任意两位数字（即，都是奇数或者偶数）。</p>\n",
    "\n",
    "<p>返回交换 <strong>任意</strong> 次之后 <code>num</code> 的 <strong>最大</strong> 可能值<em>。</em></p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>num = 1234\n",
    "<strong>输出：</strong>3412\n",
    "<strong>解释：</strong>交换数字 3 和数字 1 ，结果得到 3214 。\n",
    "交换数字 2 和数字 4 ，结果得到 3412 。\n",
    "注意，可能存在其他交换序列，但是可以证明 3412 是最大可能值。\n",
    "注意，不能交换数字 4 和数字 1 ，因为它们奇偶性不同。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>num = 65875\n",
    "<strong>输出：</strong>87655\n",
    "<strong>解释：</strong>交换数字 8 和数字 6 ，结果得到 85675 。\n",
    "交换数字 5 和数字 7 ，结果得到 87655 。\n",
    "注意，可能存在其他交换序列，但是可以证明 87655 是最大可能值。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= num &lt;= 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [largest-number-after-digit-swaps-by-parity](https://leetcode.cn/problems/largest-number-after-digit-swaps-by-parity/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [largest-number-after-digit-swaps-by-parity](https://leetcode.cn/problems/largest-number-after-digit-swaps-by-parity/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['1234', '65875']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestInteger(self, num: int) -> int:\n",
    "        l = [int(d) for d in list(str(num))]   # 转化为各位数值的数组\n",
    "        n = len(l)\n",
    "        # 进行选择排序\n",
    "        for i in range(n - 1):\n",
    "            for j in range(i + 1, n):\n",
    "                # 只有下标数值奇偶相同才进行判断\n",
    "                if (l[i] - l[j]) % 2 == 0 and l[i] < l[j]:\n",
    "                    l[i], l[j] = l[j], l[i]\n",
    "        # 转化为最终的整数\n",
    "        return int(\"\".join(str(d) for d in l))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestInteger(self, num: int) -> int:\n",
    "        lstodd = sorted([c for c in str(num) if c in '13579'], reverse = True)\n",
    "        lsteven = sorted([c for c in str(num) if c in '02468'], reverse = True)\n",
    "        lo = le = 0\n",
    "        strans = \"\"\n",
    "        for x in str(num):\n",
    "            if x in '13579':\n",
    "                strans += lstodd[lo]\n",
    "                lo += 1\n",
    "            else:\n",
    "                strans += lsteven[le]\n",
    "                le += 1\n",
    "        return int(strans)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestInteger(self, num: int) -> int:\n",
    "        a, b = [], []\n",
    "        for ch in str(num):\n",
    "            if int(ch) % 2:\n",
    "                a.append(ch)\n",
    "            else:\n",
    "                b.append(ch)\n",
    "        ans = ''\n",
    "        a.sort(reverse=True)\n",
    "        b.sort(reverse=True)\n",
    "        for ch in str(num):\n",
    "            if int(ch) % 2:\n",
    "                ans += a.pop(0)\n",
    "            else:\n",
    "                ans += b.pop(0)\n",
    "        return int(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestInteger(self, num: int) -> int:\n",
    "        index_odd = []\n",
    "        index_even = []\n",
    "        odd = []\n",
    "        even = []\n",
    "        res = ''\n",
    "        s = str(num)\n",
    "        for i in range(len(s)):\n",
    "            if int(s[i]) //2 == int(s[i])/2 :\n",
    "                index_even.append(i)\n",
    "                even.append(int(s[i]))\n",
    "            else:\n",
    "                index_odd.append(i)\n",
    "                odd.append(int(s[i]))\n",
    "        \n",
    "        for j in range(len(s)):\n",
    "            if j in index_odd:\n",
    "                res += str(odd.pop(odd.index(max(odd))))\n",
    "            else:\n",
    "                res += str(even.pop(even.index(max(even))))\n",
    "        return int(res)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestInteger(self, num: int) -> int:\n",
    "        string = str(num)\n",
    "        length = len(string)\n",
    "        even_position = []\n",
    "        even_num = []\n",
    "        odd_position = []\n",
    "        odd_num = []\n",
    "        for i in range(0, length):\n",
    "            char = string[i]\n",
    "            num = int(char)\n",
    "            if num % 2 == 0:\n",
    "                even_num.append(char)\n",
    "                even_position.append(i)\n",
    "            else:\n",
    "                odd_num.append(char)\n",
    "                odd_position.append(i)\n",
    "        even_position.sort()\n",
    "        even_num.sort(reverse=True)\n",
    "\n",
    "        odd_position.sort()\n",
    "        odd_num.sort(reverse=True)\n",
    "\n",
    "        result = \"\"\n",
    "        even_position.append(20)\n",
    "        odd_position.append(20)\n",
    "\n",
    "        even_point = 0\n",
    "        odd_point = 0\n",
    "        while even_position[even_point] != odd_position[odd_point]:\n",
    "            if even_position[even_point] < odd_position[odd_point]:\n",
    "                result = result + even_num[even_point]\n",
    "                even_point += 1\n",
    "            else:\n",
    "                result = result + odd_num[odd_point]\n",
    "                odd_point += 1\n",
    "        return int(result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestInteger(self, num: int) -> int:\n",
    "        list_1 = []\n",
    "        list_2 = []\n",
    "        flag = []\n",
    "        while num:\n",
    "            value = num%10\n",
    "            if value%2 == 0:\n",
    "                list_1.append(value)\n",
    "                flag.append(0)\n",
    "            else:\n",
    "                list_2.append(value)\n",
    "                flag.append(1)\n",
    "            num = num//10\n",
    "        list_1 = sorted(list_1)[::-1]\n",
    "        list_2 = sorted(list_2)[::-1]\n",
    "        flag = flag[::-1]\n",
    "        s , i , j= \"\" , 0 , 0\n",
    "        for k in flag:\n",
    "            if k == 0:\n",
    "                s = s + str(list_1[i])\n",
    "                i = i + 1\n",
    "            else:\n",
    "                s = s + str(list_2[j])\n",
    "                j = j + 1\n",
    "        return int(s)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestInteger(self, num: int) -> int:\n",
    "        h1,h2=[],[]\n",
    "        cur=num\n",
    "        while cur:\n",
    "            a=cur%10\n",
    "            if a%2==0:\n",
    "                heapq.heappush(h1,-a)\n",
    "            else:\n",
    "                heapq.heappush(h2,-a)\n",
    "            cur//=10\n",
    "        ans=0\n",
    "        for s in str(num):\n",
    "            a=int(s)\n",
    "            if a%2==0:\n",
    "                ans=ans*10-heapq.heappop(h1)\n",
    "            else:\n",
    "                ans=ans*10-heapq.heappop(h2)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestInteger(self, num: int) -> int:\n",
    "        nums = [int(i) for i in list(str(num))]\n",
    "        for i in range(len(nums) - 1):\n",
    "            for j in range(i+1, len(nums)):\n",
    "                if (nums[i] - nums[j])%2 == 0 and nums[j] > nums[i]:\n",
    "                    nums[i], nums[j] = nums[j], nums[i]\n",
    "        return int(\"\".join([str(i) for i in nums]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestInteger(self, num: int) -> int:\n",
    "        str_num = str(num)\n",
    "        odd = sorted([i for i in str_num if int(i)%2 != 0], reverse=True)\n",
    "        even = sorted([i for i in str_num if int(i)%2 == 0], reverse=True)\n",
    "        odd_idx, even_idx = 0, 0\n",
    "        holder = []\n",
    "        i = 0\n",
    "        while i < len(str_num):\n",
    "            if int(str_num[i])%2 == 0:\n",
    "                holder.append(even[even_idx])\n",
    "                even_idx += 1\n",
    "            else:\n",
    "                holder.append(odd[odd_idx])\n",
    "                odd_idx += 1\n",
    "            i += 1\n",
    "        return int(''.join(holder))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestInteger(self, num: int) -> int:\n",
    "        l = [int(d) for d in list(str(num))]   # 转化为各位数值的数组\n",
    "        n = len(l)\n",
    "        # 进行选择排序\n",
    "        for i in range(n - 1):\n",
    "            for j in range(i + 1, n):\n",
    "                # 只有下标数值奇偶相同才进行判断\n",
    "                if (l[i] - l[j]) % 2 == 0 and l[i] < l[j]:\n",
    "                    l[i], l[j] = l[j], l[i]\n",
    "        # 转化为最终的整数\n",
    "        return int(\"\".join(str(d) for d in l))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestInteger(self, num: int) -> int:\n",
    "        l = [int(d)for d in list(str(num))]\n",
    "        n = len(l)\n",
    "        for i in range(n-1):\n",
    "            for j in range(i+1,n):\n",
    "                if(l[i]-l[j])%2==0 and l[i]<l[j]:\n",
    "                    l[i],l[j] = l[j],l[i]\n",
    "        return int(\"\".join(str(d) for d in l))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestInteger(self, num: int) -> int:\n",
    "        s=str(num)\n",
    "        s0=[int(i) for i in list(str(num)) if int(i)%2==0]\n",
    "        s1=[int(i) for i in list(str(num)) if int(i)%2==1]\n",
    "        s0.sort()\n",
    "        s1.sort()\n",
    "        ad={}\n",
    "        res=[None for _ in range(len(str(num)))]\n",
    "        for i in range(len(s)):\n",
    "            if int(str(s[i]))%2==0:\n",
    "                ad[i]=True\n",
    "            else:\n",
    "                ad[i]=False\n",
    "        for i in ad:\n",
    "            if ad[i]==True:\n",
    "                res[i]=str(s0.pop())\n",
    "            else:\n",
    "                res[i]=str(s1.pop())\n",
    "        return int(''.join(res))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestInteger(self, num: int) -> int:\n",
    "        odds, evens, index = [], [], []\n",
    "        for v in str(num):\n",
    "            if int(v) % 2 == 0:\n",
    "                index.append(True)\n",
    "                odds.append(v)\n",
    "            else:\n",
    "                index.append(False)\n",
    "                evens.append(v)\n",
    "        odds.sort()\n",
    "        evens.sort()\n",
    "        return int(\"\".join([odds.pop() if index[x] else evens.pop() for x in range(len(index))]))\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from itertools import zip_longest\n",
    "class Solution:\n",
    "    def largestInteger(self, num: int) -> int:\n",
    "        n=[int(i) for i in str(num)]\n",
    "        x=0\n",
    "        y=1\n",
    "        while x<len(n):\n",
    "            if y>len(n)-1:\n",
    "                x+=1\n",
    "                y=x+1\n",
    "                continue\n",
    "            if n[x]%2==0 and n[y]%2!=0:\n",
    "                y+=1\n",
    "            elif n[x]%2==0 and n[y]%2==0 and n[y]>n[x]:\n",
    "                n[x],n[y]=n[y],n[x]\n",
    "                y+=1\n",
    "            elif n[x]%2!=0 and n[y]%2==0:\n",
    "                y+=1\n",
    "            elif  n[x]%2!=0 and n[y]%2!=0 and n[y]>n[x]:\n",
    "                n[x], n[y] = n[y], n[x]\n",
    "                y+=1\n",
    "            else:\n",
    "                y+=1\n",
    "        return int(''.join([str(i) for i in n]))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def largestInteger(self, num: int) -> int:\n",
    "\n",
    "#         lst1,lst2=[],[]\n",
    "#         while num:\n",
    "#             lst1.append(num%10)\n",
    "#             num//=10\n",
    "#             if num:\n",
    "#                 lst2.append(num%10)\n",
    "#                 num//=10\n",
    "        \n",
    "#         lst1.sort(reverse=True)\n",
    "#         lst2.sort(reverse=True)\n",
    "\n",
    "#         if len(lst1)>len(lst2):\n",
    "#             lst1,lst2=lst2,lst1\n",
    "\n",
    "#         res=0\n",
    "#         n=len(lst1)\n",
    "#         for i in range(len(lst2)):\n",
    "#             res=res*10+lst2[i]\n",
    "#             if i<n:\n",
    "#                 res=res*10+lst1[i]\n",
    "#         return res\n",
    "\n",
    "# class Solution:\n",
    "#     def largestInteger(self, num: int) -> int:\n",
    "#         lst1,lst2=[],[]\n",
    "#         idx=[]\n",
    "#         cnt=0\n",
    "#         while num:\n",
    "#             cnt-=1\n",
    "#             tmp=num%10\n",
    "#             if tmp%2:\n",
    "#                 idx.append(cnt)\n",
    "#                 lst1.append(tmp)\n",
    "#             else:\n",
    "#                 lst2.append(tmp)\n",
    "#             num//=10\n",
    "\n",
    "#         m,n=len(lst1),len(lst2)\n",
    "#         le=m+n\n",
    "#         for i,k in enumerate(idx):\n",
    "#             idx[i]=le-k\n",
    "        \n",
    "#         lst1.sort()\n",
    "#         lst2.sort()\n",
    "#         i,j=m-1,n-1\n",
    "#         res=0\n",
    "#         for k in range(le):\n",
    "#             if k not in idx:\n",
    "#                 res=res*10+lst2[j]\n",
    "#                 j-=1\n",
    "#             else:\n",
    "#                 res=res*10+lst1[i]\n",
    "#                 i-=1\n",
    "#         return res\n",
    "\n",
    "# ### 官解：10**9可以转化为字符串，不超值？？\n",
    "# class Solution:\n",
    "#     def largestInteger(self,num):\n",
    "#         lst=[int(d) for d in list(str(num))]\n",
    "\n",
    "#         n=len(lst)\n",
    "#         for i in range(n-1):\n",
    "#             for j in range(i+1,n):\n",
    "#                 ### 负偶数与2取余，也是0\n",
    "#                 if (lst[i]-lst[j])%2==0 and lst[i]<lst[j]:\n",
    "#                     lst[i],lst[j]=lst[j],lst[i]\n",
    "        \n",
    "#         return int(\"\".join(str(d) for d in lst))\n",
    "\n",
    "\n",
    "### 官解：排序（原码）\n",
    "class Solution:\n",
    "    def largestInteger(self, num: int) -> int:\n",
    "        l = [int(d) for d in list(str(num))]   # 转化为各位数值的数组\n",
    "        n = len(l)\n",
    "        # 进行选择排序\n",
    "        for i in range(n - 1):\n",
    "            for j in range(i + 1, n):\n",
    "                # 只有下标数值奇偶相同才进行判断\n",
    "                if (l[i] - l[j]) % 2 == 0 and l[i] < l[j]:\n",
    "                    l[i], l[j] = l[j], l[i]\n",
    "        # 转化为最终的整数\n",
    "        return int(\"\".join(str(d) for d in l))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestInteger(self, num: int) -> int:\n",
    "        s = str(num)\n",
    "        num_o, num_e = [], []\n",
    "        for i in s:\n",
    "            if int(i) % 2:\n",
    "                num_o.append(int(i))\n",
    "            else:\n",
    "                num_e.append(int(i))\n",
    "        num_o.sort()\n",
    "        num_e.sort()\n",
    "        ans = ''\n",
    "        for i in s:\n",
    "            if int(i) % 2:\n",
    "                ans = ans + str(num_o.pop())\n",
    "            else:\n",
    "                ans = ans + str(num_e.pop())\n",
    "        return int(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestInteger(self, num: int) -> int:\n",
    "        l = [int(d) for d in list(str(num))]   # 转化为各位数值的数组\n",
    "        n = len(l)\n",
    "        # 进行选择排序\n",
    "        for i in range(n - 1):\n",
    "            for j in range(i + 1, n):\n",
    "                # 只有下标数值奇偶相同才进行判断\n",
    "                if (l[i] - l[j]) % 2 == 0 and l[i] < l[j]:\n",
    "                    l[i], l[j] = l[j], l[i]\n",
    "        # 转化为最终的整数\n",
    "        return int(\"\".join(str(d) for d in l))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestInteger(self, num: int) -> int:\n",
    "        s = str(num)\n",
    "        symbol = [False] * len(s)\n",
    "        qishu = []\n",
    "        oushu = []\n",
    "        for index,value in enumerate(s):\n",
    "            if int(value) % 2:\n",
    "                symbol[index] = True\n",
    "                qishu.append(int(value))\n",
    "            else:\n",
    "                oushu.append(int(value))\n",
    "        qishu.sort(reverse = True)\n",
    "        oushu.sort(reverse = True)\n",
    "        ans = ''\n",
    "        for sym in symbol:\n",
    "            if sym:\n",
    "                ans = ans + str(qishu.pop(0))\n",
    "            else:\n",
    "                ans = ans + str(oushu.pop(0))\n",
    "        return int(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestInteger(self, num: int) -> int:\n",
    "        odds, evens, index = [], [], []\n",
    "        for v in str(num):\n",
    "            if int(v) % 2 == 0:\n",
    "                index.append(True)\n",
    "                odds.append(v)\n",
    "            else:\n",
    "                index.append(False)\n",
    "                evens.append(v)\n",
    "        odds.sort()\n",
    "        evens.sort()\n",
    "        return int(\"\".join([odds.pop() if index[x] else evens.pop() for x in range(len(index))]))\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestInteger(self, num: int) -> int:\n",
    "        lst = list(str(num))\n",
    "        lst_i, lst_0, lst_1 = [], [], []\n",
    "        for n in lst:\n",
    "            if int(n) % 2 == 0:\n",
    "                lst_i.append(0)\n",
    "                lst_0.append(int(n))\n",
    "            else:\n",
    "                lst_i.append(1)\n",
    "                lst_1.append(int(n))\n",
    "        lst_0.sort(reverse=True)\n",
    "        lst_1.sort(reverse=True)\n",
    "        ans = []\n",
    "        m, n = 0, 0\n",
    "        for i in lst_i:\n",
    "            if i == 1:\n",
    "                ans.append(str(lst_1[m]))\n",
    "                m += 1\n",
    "            else:\n",
    "                ans.append(str(lst_0[n]))\n",
    "                n += 1\n",
    "        return int(\"\".join(ans))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestInteger(self, num: int) -> int:\n",
    "        odds = []\n",
    "        evens = []\n",
    "        shunxu = []\n",
    "        new = 0\n",
    "        while num != 0:\n",
    "            d = num % 10\n",
    "            if d % 2 != 0:\n",
    "                odds.append(d)\n",
    "                shunxu.append(1)\n",
    "            else:\n",
    "                evens.append(d)\n",
    "                shunxu.append(0)\n",
    "            num = num // 10\n",
    "        odds.sort(reverse=True)\n",
    "        evens.sort(reverse=True)\n",
    "        shunxu.reverse()\n",
    "        o = 0\n",
    "        d = 0\n",
    "        for i in shunxu:\n",
    "            if i == 1:\n",
    "                new = new * 10 + odds[o]\n",
    "                o = o + 1\n",
    "            else:\n",
    "                new = new * 10 + evens[d]\n",
    "                d = d + 1\n",
    "        return new"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestInteger(self, num: int) -> int:\n",
    "        nums1,nums2=sorted([int(x) for x in str(num) if x in '13579']),sorted([int(x) for x in str(num) if x in '02468'])      \n",
    "        return int(''.join(map(str,[nums1.pop() if int(x)&1 else nums2.pop() for x in str(num)])))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestInteger(self, num: int) -> int:\n",
    "        arr = [] \n",
    "        while num :\n",
    "            arr.append(num % 10)\n",
    "            num //= 10\n",
    "\n",
    "        even = []\n",
    "        odd = []\n",
    "        even_idx = set()\n",
    "        odd_idx = set()\n",
    "        for i, a in enumerate(arr):\n",
    "            if a % 2 == 0:\n",
    "                even.append(a)\n",
    "                even_idx.add(i)\n",
    "            else:\n",
    "                odd.append(a)\n",
    "                odd_idx.add(i)\n",
    "\n",
    "        even.sort()\n",
    "        odd.sort()\n",
    "\n",
    "        new_arr = []\n",
    "\n",
    "        i1, i2 = 0, 0\n",
    "        for i in range(len(arr)):\n",
    "            if i in even_idx:\n",
    "                new_arr.append(even[i1])\n",
    "                i1 += 1\n",
    "            else:\n",
    "                new_arr.append(odd[i2])\n",
    "                i2 += 1\n",
    "\n",
    "        res = 0 \n",
    "        for i in new_arr[::-1]:\n",
    "            res = res* 10 + i  \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestInteger(self, num: int) -> int:\n",
    "        odd = []\n",
    "        even = []\n",
    "        for i in str(num):\n",
    "            if int(i) % 2 == 1:\n",
    "                odd.append(int(i))\n",
    "            elif int(i) % 2 == 0:\n",
    "                even.append(int(i))\n",
    "        \n",
    "        odd.sort(reverse=True)\n",
    "        even.sort(reverse=True)\n",
    "        res= []\n",
    "\n",
    "        for i in range(len(str(num))):\n",
    "            if int(str(num)[i]) % 2 == 1:\n",
    "                res.append(str(odd[0]))\n",
    "                odd.pop(0)\n",
    "\n",
    "            elif int(str(num)[i]) % 2 == 0:\n",
    "                res.append(str(even[0]))\n",
    "                even.pop(0)\n",
    "\n",
    "        return int(''.join(res))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestInteger(self, num: int) -> int:\n",
    "        l = [int(d) for d in list(str(num))]   # 转化为各位数值的数组\n",
    "        n = len(l)\n",
    "        # 进行选择排序\n",
    "        for i in range(n - 1):\n",
    "            for j in range(i + 1, n):\n",
    "                # 只有下标数值奇偶相同才进行判断\n",
    "                if (l[i] - l[j]) % 2 == 0 and l[i] < l[j]:\n",
    "                    l[i], l[j] = l[j], l[i]\n",
    "        # 转化为最终的整数\n",
    "        return int(\"\".join(str(d) for d in l))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestInteger(self, num: int) -> int:\n",
    "        l = [int(d) for d in list(str(num))]   # 转化为各位数值的数组\n",
    "        n = len(l)\n",
    "        # 进行选择排序\n",
    "        for i in range(n - 1):\n",
    "            for j in range(i + 1, n):\n",
    "                # 只有下标数值奇偶相同才进行判断\n",
    "                if (l[i] - l[j]) % 2 == 0 and l[i] < l[j]:\n",
    "                    l[i], l[j] = l[j], l[i]\n",
    "        # 转化为最终的整数\n",
    "        return int(\"\".join(str(d) for d in l))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestInteger(self, num: int) -> int:\n",
    "        odd = sorted([i for i in str(num) if i in '13579'],reverse=True)\n",
    "        even = sorted([i for i in str(num) if i in '02468'],reverse=True)\n",
    "        res = ''\n",
    "        idx1=idx2 = 0\n",
    "        for x in str(num):\n",
    "            if x in '13579':      # 利用原数组中的奇偶顺序\n",
    "                res += odd[idx1]\n",
    "                idx1 += 1\n",
    "            else:\n",
    "                res += even[idx2]\n",
    "                idx2 += 1\n",
    "        return int(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestInteger(self, num: int) -> int:\n",
    "        string = str(num)\n",
    "        length = len(string)\n",
    "        even_position = []\n",
    "        even_num = []\n",
    "        odd_position = []\n",
    "        odd_num = []\n",
    "        for i in range(0, length):\n",
    "            char = string[i]\n",
    "            num = int(char)\n",
    "            if num % 2 == 0:\n",
    "                even_num.append(char)\n",
    "                even_position.append(i)\n",
    "            else:\n",
    "                odd_num.append(char)\n",
    "                odd_position.append(i)\n",
    "        even_position.sort()\n",
    "        even_num.sort(reverse=True)\n",
    "\n",
    "        odd_position.sort()\n",
    "        odd_num.sort(reverse=True)\n",
    "\n",
    "        result = \"\"\n",
    "        even_position.append(20)\n",
    "        odd_position.append(20)\n",
    "\n",
    "        even_point = 0\n",
    "        odd_point = 0\n",
    "        while even_position[even_point] != odd_position[odd_point]:\n",
    "            if even_position[even_point] < odd_position[odd_point]:\n",
    "                result = result + even_num[even_point]\n",
    "                even_point += 1\n",
    "            else:\n",
    "                result = result + odd_num[odd_point]\n",
    "                odd_point += 1\n",
    "        return int(result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def largestInteger(self, num: int) -> int:\n",
    "\n",
    "#         lst1,lst2=[],[]\n",
    "#         while num:\n",
    "#             lst1.append(num%10)\n",
    "#             num//=10\n",
    "#             if num:\n",
    "#                 lst2.append(num%10)\n",
    "#                 num//=10\n",
    "        \n",
    "#         lst1.sort(reverse=True)\n",
    "#         lst2.sort(reverse=True)\n",
    "\n",
    "#         if len(lst1)>len(lst2):\n",
    "#             lst1,lst2=lst2,lst1\n",
    "\n",
    "#         res=0\n",
    "#         n=len(lst1)\n",
    "#         for i in range(len(lst2)):\n",
    "#             res=res*10+lst2[i]\n",
    "#             if i<n:\n",
    "#                 res=res*10+lst1[i]\n",
    "#         return res\n",
    "\n",
    "# class Solution:\n",
    "#     def largestInteger(self, num: int) -> int:\n",
    "#         lst1,lst2=[],[]\n",
    "#         idx=[]\n",
    "#         cnt=0\n",
    "#         while num:\n",
    "#             cnt-=1\n",
    "#             tmp=num%10\n",
    "#             if tmp%2:\n",
    "#                 idx.append(cnt)\n",
    "#                 lst1.append(tmp)\n",
    "#             else:\n",
    "#                 lst2.append(tmp)\n",
    "#             num//=10\n",
    "\n",
    "#         m,n=len(lst1),len(lst2)\n",
    "#         le=m+n\n",
    "#         for i,k in enumerate(idx):\n",
    "#             idx[i]=le-k\n",
    "        \n",
    "#         lst1.sort()\n",
    "#         lst2.sort()\n",
    "#         i,j=m-1,n-1\n",
    "#         res=0\n",
    "#         for k in range(le):\n",
    "#             if k not in idx:\n",
    "#                 res=res*10+lst2[j]\n",
    "#                 j-=1\n",
    "#             else:\n",
    "#                 res=res*10+lst1[i]\n",
    "#                 i-=1\n",
    "#         return res\n",
    "\n",
    "### 官解：10**9可以转化为字符串，不超值？？\n",
    "class Solution:\n",
    "    def largestInteger(self,num):\n",
    "        lst=[int(d) for d in list(str(num))]\n",
    "\n",
    "        n=len(lst)\n",
    "        for i in range(n-1):\n",
    "            for j in range(i+1,n):\n",
    "                ### 负偶数与2取余，也是0\n",
    "                if (lst[i]-lst[j])%2==0 and lst[i]<lst[j]:\n",
    "                    lst[i],lst[j]=lst[j],lst[i]\n",
    "        \n",
    "        return int(\"\".join(str(d) for d in lst))\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestInteger(self, num: int) -> int:\n",
    "        odds = []\n",
    "        evens = []\n",
    "        index = []\n",
    "        for v in str(num):\n",
    "            if int(v) % 2 == 0:\n",
    "                index.append(True)\n",
    "                odds.append(v)\n",
    "            else:\n",
    "                index.append(False)\n",
    "                evens.append(v)\n",
    "        odds.sort()\n",
    "        evens.sort()\n",
    "        return int(\"\".join([odds.pop() if index[x] else evens.pop() for x in range(len(index))]))\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestInteger(self, num: int) -> int:\n",
    "        odd, even, total = [], [], []\n",
    "        \n",
    "        \n",
    "        while num:\n",
    "            a = num % 10\n",
    "            if a % 2:\n",
    "                odd.append(a)\n",
    "                total.append(1)\n",
    "            else:\n",
    "                even.append(a) \n",
    "                total.append(0)\n",
    "                \n",
    "            num //= 10\n",
    "            \n",
    "        odd.sort()\n",
    "        even.sort()\n",
    "        \n",
    "               \n",
    "        res = 0\n",
    "        n = len(total)\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            if total[i]:\n",
    "                res += odd.pop() * 10 ** i\n",
    "            else:\n",
    "                res += even.pop() * 10 ** i\n",
    "        return res\n",
    "          \n",
    "        \n",
    "            \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestInteger(self, num: int) -> int:\n",
    "        l = []\n",
    "        while num > 0:\n",
    "            l.append(num % 10)\n",
    "            num //= 10\n",
    "        l.reverse()\n",
    "        odd = sorted(n for n in l if n & 1)\n",
    "        even = sorted(n for n in l if not n & 1)\n",
    "        ans = 0\n",
    "        for i, n in enumerate(l):\n",
    "            ans *= 10\n",
    "            ans += odd.pop() if n & 1 else even.pop()\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestInteger(self, num: int) -> int:\n",
    "        l = [int(d) for d in list(str(num))]   # 转化为各位数值的数组\n",
    "        n = len(l)\n",
    "        # 进行选择排序\n",
    "        for i in range(n - 1):\n",
    "            for j in range(i + 1, n):\n",
    "                # 只有下标数值奇偶相同才进行判断\n",
    "                if (l[i] - l[j]) % 2 == 0 and l[i] < l[j]:\n",
    "                    l[i], l[j] = l[j], l[i]\n",
    "        # 转化为最终的整数\n",
    "        return int(\"\".join(str(d) for d in l))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestInteger(self, num: int) -> int:\n",
    "        odd=[]\n",
    "        even=[]\n",
    "        s=str(num)\n",
    "        for i in s:\n",
    "            if int(i)%2==0:\n",
    "                odd.append(i)\n",
    "            else:\n",
    "                even.append(i)\n",
    "        odd.sort(reverse=True)\n",
    "        even.sort(reverse=True)\n",
    "        result=\"\"\n",
    "        index_odd=0\n",
    "        index_even=0\n",
    "        for i in s:\n",
    "            if int(i)%2==0:\n",
    "                result+=odd[index_odd]\n",
    "                index_odd+=1\n",
    "            else:\n",
    "                result+=even[index_even]\n",
    "                index_even+=1\n",
    "        return int(result)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestInteger(self, num: int) -> int:\n",
    "        if num < 10:\n",
    "            return num\n",
    "        tmp = num\n",
    "        s1, s2 = [], []\n",
    "        while num:\n",
    "            t = num % 10\n",
    "            num //= 10\n",
    "            if t % 2 == 0:\n",
    "                s1.append(t)\n",
    "            else:\n",
    "                s2.append(t)\n",
    "        s1.sort()\n",
    "        s2.sort()\n",
    "        ans = 0\n",
    "        for x in str(tmp):\n",
    "            if int(x) % 2 == 0:\n",
    "                ans = ans * 10 + s1.pop()\n",
    "            else:\n",
    "                ans = ans * 10 + s2.pop()\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestInteger(self, num: int) -> int:\n",
    "        nums = [int(d) for d in list(str(num))]\n",
    "        n = len(nums)\n",
    "        for i in range(n-1):\n",
    "            for j in range(i+1,n):\n",
    "                if (nums[i]-nums[j])%2==0 and nums[i]<nums[j]:\n",
    "                    nums[i],nums[j] = nums[j],nums[i]\n",
    "        return int(''.join(str(d) for d in nums))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestInteger(self, num: int) -> int:\n",
    "        heap_1 = [] # odd\n",
    "        heap_2 = [] # even\n",
    "        import heapq as hp\n",
    "        txt = list(map(int,str(num)))\n",
    "        n=len(txt)\n",
    "        for i in range(n):\n",
    "            if txt[i] % 2 ==0:\n",
    "                hp.heappush(heap_2,-txt[i])\n",
    "            if txt[i] % 2 ==1:\n",
    "                hp.heappush(heap_1,-txt[i])\n",
    "        \n",
    "        for i in range(n):\n",
    "            if txt[i] %2==0:\n",
    "                txt[i]= -heappop(heap_2)\n",
    "            if txt[i] %2==1:\n",
    "                txt[i]= -heappop(heap_1)\n",
    "        \n",
    "        return int(''.join(map(str,txt)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestInteger(self, num: int) -> int:\n",
    "        l = []\n",
    "        while num > 0:\n",
    "            l.append(num % 10)\n",
    "            num //= 10\n",
    "        l.reverse()\n",
    "        odd = []\n",
    "        even = []\n",
    "        for n in l:\n",
    "            if n & 1:\n",
    "                odd.append(n)\n",
    "            else:\n",
    "                even.append(n)\n",
    "        odd.sort()\n",
    "        even.sort()\n",
    "        ans = 0\n",
    "        for i, n in enumerate(l):\n",
    "            ans *= 10\n",
    "            if n & 1:\n",
    "                ans += odd.pop()\n",
    "            else:\n",
    "                ans += even.pop()\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestInteger(self, num: int) -> int:\n",
    "        string = str(num)\n",
    "        length = len(string)\n",
    "        even_position = []\n",
    "        even_num = []\n",
    "        odd_position = []\n",
    "        odd_num = []\n",
    "        for i in range(0, length):\n",
    "            char = string[i]\n",
    "            num = int(char)\n",
    "            if num % 2 == 0:\n",
    "                even_num.append(char)\n",
    "                even_position.append(i)\n",
    "            else:\n",
    "                odd_num.append(char)\n",
    "                odd_position.append(i)\n",
    "        even_position.sort()\n",
    "        even_num.sort(reverse=True)\n",
    "\n",
    "        odd_position.sort()\n",
    "        odd_num.sort(reverse=True)\n",
    "\n",
    "        result = \"\"\n",
    "        even_position.append(20)\n",
    "        odd_position.append(20)\n",
    "\n",
    "        even_point = 0\n",
    "        odd_point = 0\n",
    "        while even_position[even_point] != odd_position[odd_point]:\n",
    "            if even_position[even_point] < odd_position[odd_point]:\n",
    "                result = result + even_num[even_point]\n",
    "                even_point += 1\n",
    "            else:\n",
    "                result = result + odd_num[odd_point]\n",
    "                odd_point += 1\n",
    "        return int(result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestInteger(self, num: int) -> int:\n",
    "        li = list(map(int,str(num)))\n",
    "        odds = []\n",
    "        evens = []\n",
    "        for i, n in enumerate(li):\n",
    "            if n % 2: odds.append(i)\n",
    "            else: evens.append(i)\n",
    "        def change(li, indexes):\n",
    "            for i in range(len(indexes) - 1):\n",
    "                tmp = li[indexes[i]]\n",
    "                idx = i\n",
    "                for j in range(i + 1, len(indexes)):\n",
    "                    if(li[indexes[j]] > tmp):\n",
    "                        tmp = li[indexes[j]]\n",
    "                        idx = j\n",
    "                li[indexes[i]], li[indexes[idx]] = li[indexes[idx]], li[indexes[i]]\n",
    "                indexes[i], indexes[idx] = indexes[j],indexes[idx]\n",
    "        change(li,odds)\n",
    "        change(li,evens)\n",
    "        ans = 0\n",
    "        for i in range(len(li)):\n",
    "            ans = ans * 10 + li[i]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestInteger(self, num: int) -> int:\n",
    "        odds = []\n",
    "        evens = []\n",
    "        index = []\n",
    "        for v in str(num):\n",
    "            if int(v) % 2 == 0:\n",
    "                index.append(True)\n",
    "                odds.append(v)\n",
    "            else:\n",
    "                index.append(False)\n",
    "                evens.append(v)\n",
    "        odds.sort()\n",
    "        evens.sort()\n",
    "        ans = \"\"\n",
    "        for i in range(len(index)):\n",
    "            if index[i]:\n",
    "                ans += odds.pop()\n",
    "            else:\n",
    "                ans += evens.pop()\n",
    "        return int(ans)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestInteger(self, num: int) -> int:\n",
    "        a = [ord(x) - ord('0') for x in str(num)]\n",
    "        ans = []\n",
    "        odd = [x for x in a if x % 2]\n",
    "        even = [x for x in a if x % 2 == 0]\n",
    "        odd.sort(key = lambda x:-x)\n",
    "        even.sort(key = lambda x:-x)\n",
    "        i, j = 0, 0\n",
    "        for x in a:\n",
    "            if x % 2 == 0:\n",
    "                ans.append(even[j])\n",
    "                j += 1\n",
    "            else:\n",
    "                ans.append(odd[i])\n",
    "                i += 1\n",
    "        return int(\"\".join([chr(ord('0') +x) for x in ans]))\n",
    "            \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestInteger(self, num: int) -> int:\n",
    "        digits = []\n",
    "        temp_num = num\n",
    "        while temp_num != 0:\n",
    "            digits.append(temp_num % 10)\n",
    "            temp_num //= 10\n",
    "        odd_digits = [digit for digit in digits if digit % 2 == 1]\n",
    "        even_digits = [digit for digit in digits if digit % 2 == 0]\n",
    "        odd_digits.sort(reverse=True)\n",
    "        even_digits.sort(reverse=True)\n",
    "        odd_pointer, even_pointer = 0, 0\n",
    "        for i in range(len(digits) - 1, -1, -1):\n",
    "            if digits[i] % 2 == 1:\n",
    "                digits[i] = odd_digits[odd_pointer]\n",
    "                odd_pointer += 1\n",
    "            else:\n",
    "                digits[i] = even_digits[even_pointer]\n",
    "                even_pointer += 1\n",
    "        num = 0\n",
    "        for i in range(len(digits) - 1, -1, -1):\n",
    "            num = num * 10 + digits[i]\n",
    "        return num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestInteger(self, num: int) -> int:\n",
    "        l = []\n",
    "        while num > 0:\n",
    "            l.append(num % 10)\n",
    "            num //= 10\n",
    "        l.reverse()\n",
    "        odd = sorted(n for n in l if n & 1)\n",
    "        even = sorted(n for n in l if not n & 1)\n",
    "        ans = 0\n",
    "        for n in l:\n",
    "            ans *= 10\n",
    "            ans += odd.pop() if n & 1 else even.pop()\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestInteger(self, num: int) -> int:\n",
    "        nums1 = [int(x)  for x in str(num) if int(x) % 2 == 1]\n",
    "        nums2 = [int(x)  for x in str(num) if int(x) % 2 == 0]\n",
    "        nums1.sort()\n",
    "        nums2.sort()\n",
    "        ans = []\n",
    "        for x in str(num):\n",
    "            if int(x) % 2 == 1:\n",
    "                ans.append(nums1.pop())\n",
    "            else:\n",
    "                ans.append(nums2.pop())\n",
    "        return int(\"\".join([str(x) for x in ans]))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestInteger(self, num: int) -> int:\n",
    "        nums=[int(i)for i in list(str(num))]\n",
    "        n=len(nums)\n",
    "        for i in range(n-1):\n",
    "            for j in range(i+1,n):\n",
    "                if nums[i]%2==nums[j]%2 and nums[i]<nums[j]:\n",
    "                    nums[i],nums[j]=nums[j],nums[i]\n",
    "        return int(''.join(str(i)for i in nums))\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestInteger(self, num: int) -> int:\n",
    "        lst = list(str(num))\n",
    "        lst_i, lst_0, lst_1 = [], [], []\n",
    "        for n in lst:\n",
    "            if int(n) % 2 == 0:\n",
    "                lst_i.append(0)\n",
    "                lst_0.append(n)\n",
    "            else:\n",
    "                lst_i.append(1)\n",
    "                lst_1.append(n)\n",
    "        lst_0.sort()\n",
    "        lst_1.sort()\n",
    "        ans = []\n",
    "        for i in lst_i:\n",
    "            if i == 1:\n",
    "                ans.append(lst_1[-1])\n",
    "                lst_1.pop()\n",
    "            else:\n",
    "                ans.append(lst_0[-1])\n",
    "                lst_0.pop()\n",
    "        return int(\"\".join(ans))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestInteger(self, num: int) -> int:\n",
    "\n",
    "\n",
    "        date_list = []\n",
    "        for date in str(num):\n",
    "            date_list.append(int(date))\n",
    "\n",
    "        print(date_list)\n",
    "        date_len = len(date_list)\n",
    "        count = 0\n",
    "\n",
    "        for i in range(0, date_len - 1):\n",
    "        \n",
    "            count = 0\n",
    "            date_i = date_list[i]\n",
    "\n",
    "            for j in range(i, date_len):\n",
    "            \n",
    "                date_j = date_list[j]\n",
    "\n",
    "                if date_j % 2 == 0 and date_i % 2 == 0:\n",
    "                    if date_j > count:\n",
    "                        count = date_j\n",
    "                        date_list[i], date_list[j] = date_list[j], date_list[i]\n",
    "\n",
    "                if date_j % 2 == 1 and date_i % 2 == 1:\n",
    "                    if date_j > count:\n",
    "                        count = date_j\n",
    "                        date_list[i], date_list[j] = date_list[j], date_list[i]\n",
    "\n",
    "\n",
    "        s = ''\n",
    "        for date in date_list:\n",
    "            s += str(date)\n",
    "\n",
    "        return int(s)    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from heapq import heappush, heappop\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def largestInteger(self, num: int) -> int:\n",
    "        m1 = []\n",
    "        m2 = []\n",
    "        num = str(num)\n",
    "        for n in num:\n",
    "            x = int(n)\n",
    "            heappush(m1 if x % 2 == 0 else m2, -x)\n",
    "        res = \"\"\n",
    "        for n in num:\n",
    "            x = int(n)\n",
    "            res += str(-heappop(m1 if x % 2 == 0 else m2))\n",
    "        return int(res)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestInteger(self, num: int) -> int:\n",
    "        s = list(str(num))\n",
    "        n = len(s)\n",
    "        for i in range(n):\n",
    "            idx = i\n",
    "            for j in range(i + 1, n):\n",
    "                if int(s[idx]) & 1 == int(s[j]) & 1 and s[j] > s[idx]:\n",
    "                    idx = j\n",
    "            s[i], s[idx] = s[idx], s[i]\n",
    "            # print(i, s)\n",
    "        return int(\"\".join(s))\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestInteger(self, num: int) -> int:\n",
    "        nums = list(map(int, str(num)))\n",
    "        n = len(nums)\n",
    "        lst = [0] * n\n",
    "        even = []\n",
    "        odd = []\n",
    "        e_idx = []\n",
    "        o_idx = []\n",
    "        for i in range(n):\n",
    "            if nums[i] % 2 == 0:\n",
    "                even.append(nums[i])\n",
    "                e_idx.append(i)\n",
    "            else:\n",
    "                odd.append(nums[i])\n",
    "                o_idx.append(i)\n",
    "        even.sort(reverse=True)\n",
    "        odd.sort(reverse=True)\n",
    "        for j, val1 in zip(e_idx, even):\n",
    "            lst[j] = val1\n",
    "        for k, val2 in zip(o_idx, odd):\n",
    "            lst[k] = val2\n",
    "        return int(''.join(list(map(str,lst))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestInteger(self, num: int) -> int:\n",
    "        odd, even, total = [], [], []\n",
    "        \n",
    "        \n",
    "        while num:\n",
    "            a = num % 10\n",
    "            if a % 2:\n",
    "                odd.append(a)\n",
    "                total.append(1)\n",
    "            else:\n",
    "                even.append(a) \n",
    "                total.append(0)\n",
    "                \n",
    "            num //= 10\n",
    "            \n",
    "        odd.sort()\n",
    "        even.sort()\n",
    "        \n",
    "               \n",
    "        res = 0\n",
    "        n = len(total)\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            if total[i]:\n",
    "                res += odd.pop() * 10 ** i\n",
    "            else:\n",
    "                res += even.pop() * 10 ** i\n",
    "        return res\n",
    "          \n",
    "        \n",
    "            \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestInteger(self, num: int) -> int:\n",
    "        odds = []\n",
    "        evens = []\n",
    "        index = []\n",
    "        for v in str(num):\n",
    "            if int(v) % 2 == 0:\n",
    "                index.append(True)\n",
    "                odds.append(v)\n",
    "            else:\n",
    "                index.append(False)\n",
    "                evens.append(v)\n",
    "        odds.sort()\n",
    "        evens.sort()\n",
    "        ans = \"\"\n",
    "        for i in range(len(index)):\n",
    "            if index[i]:\n",
    "                ans += odds.pop()\n",
    "            else:\n",
    "                ans += evens.pop()\n",
    "        return int(ans)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestInteger(self, num: int) -> int:\n",
    "        a = [int(d) for d in list(str(num))]\n",
    "        print(f'{a}')\n",
    "        n = len(a)\n",
    "        for i in range(n - 1):\n",
    "            for j in range(i + 1, n):\n",
    "                if (a[i] - a[j]) % 2 == 0 and a[i] < a[j]:\n",
    "                    a[i], a[j] = a[j], a[i]\n",
    "        return int(\"\".join(str(d) for d in a))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestInteger(self, num: int) -> int:\n",
    "        ji=[]\n",
    "        ou=[]\n",
    "        for i in str(num):\n",
    "            if int(i)%2==0:\n",
    "                ou.append(int(i))\n",
    "            else:\n",
    "                ji.append(int(i))\n",
    "        ji.sort(reverse=True)\n",
    "        ou.sort(reverse=True)\n",
    "        l=r=0\n",
    "        s=''\n",
    "        for i in str(num):\n",
    "            if int(i)%2==0:\n",
    "                s+=str(ou[l])\n",
    "                l+=1\n",
    "            else:\n",
    "                s+=str(ji[r])\n",
    "                r+=1\n",
    "        return int(s)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestInteger(self, num: int) -> int:\n",
    "        odds, evens, index = [], [], []\n",
    "        for v in str(num):\n",
    "            if int(v) % 2 == 0:\n",
    "                index.append(True)\n",
    "                odds.append(v)\n",
    "            else:\n",
    "                index.append(False)\n",
    "                evens.append(v)\n",
    "        odds.sort()\n",
    "        evens.sort()\n",
    "        return int(\"\".join([odds.pop() if index[x] else evens.pop() for x in range(len(index))]))\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestInteger(self, num: int) -> int:\n",
    "        ns = []\n",
    "        while num:\n",
    "            ns.append(num%10)\n",
    "            num //= 10\n",
    "        ns = ns[::-1]\n",
    "        ns1,ns2 = sorted([int(x) for x in ns if int(x) % 2],reverse=True),sorted([int(x) for x in ns if not int(x) % 2],reverse=True)\n",
    "        ans,i1,i2 = 0,0,0\n",
    "        for i in range(len(ns)):\n",
    "            ans *= 10\n",
    "            if ns[i] % 2:\n",
    "                ans += ns1[i1]\n",
    "                i1 += 1\n",
    "            else:\n",
    "                ans += ns2[i2]\n",
    "                i2 += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestInteger(self, num: int) -> int:\n",
    "        lst = list(str(num))\n",
    "        lst_i, lst_0, lst_1 = [], [], []\n",
    "        for n in lst:\n",
    "            if int(n) % 2 == 0:\n",
    "                lst_i.append(0)\n",
    "                lst_0.append(int(n))\n",
    "            else:\n",
    "                lst_i.append(1)\n",
    "                lst_1.append(int(n))\n",
    "        lst_0.sort(reverse=True)\n",
    "        lst_1.sort(reverse=True)\n",
    "        ans = []\n",
    "        m, n = 0, 0\n",
    "        for i in lst_i:\n",
    "            if i == 1:\n",
    "                ans.append(str(lst_1[m]))\n",
    "                m += 1\n",
    "            else:\n",
    "                ans.append(str(lst_0[n]))\n",
    "                n += 1\n",
    "        return int(\"\".join(ans))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestInteger(self, num: int) -> int:\n",
    "        奇数列表 = []\n",
    "        偶数列表 = []\n",
    "        顺序列表 = list(str(num))\n",
    "        for i in 顺序列表:\n",
    "            if int(i)&1:\n",
    "                奇数列表.append(int(i))\n",
    "            else:\n",
    "                偶数列表.append(int(i))\n",
    "        奇数列表.sort()\n",
    "        偶数列表.sort()\n",
    "        最大数字 = 0\n",
    "        for i in 顺序列表:\n",
    "            if int(i)&1:\n",
    "                最大数字 *= 10\n",
    "                最大数字 += 奇数列表.pop()\n",
    "            else:\n",
    "                最大数字 *= 10\n",
    "                最大数字 += 偶数列表.pop()\n",
    "        return 最大数字"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestInteger(self, num: int) -> int:\n",
    "        ls=[[],[]]\n",
    "        mark=[0]*len(str(num))\n",
    "        for i,n in enumerate(str(num)):\n",
    "            if int(n)%2==0:\n",
    "                ls[0].append(n)\n",
    "            else:\n",
    "                ls[1].append(n)\n",
    "                mark[i]=1\n",
    "        ls[0].sort(reverse=True)\n",
    "        ls[1].sort(reverse=True)\n",
    "        i,j=0,0\n",
    "        ret=\"\"\n",
    "        for k in range(len(str(num))):\n",
    "            if mark[k]==0:\n",
    "                ret+=ls[0][i]\n",
    "                i+=1\n",
    "            else:\n",
    "                ret+=ls[1][j]\n",
    "                j+=1\n",
    "        return int(ret)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestInteger(self, num: int) -> int:\n",
    "        nums1,nums2=sorted([int(x) for x in str(num) if x in '13579']),sorted([int(x) for x in str(num) if x in '02468'])      \n",
    "        return int(''.join(map(str,[nums1.pop() if int(x)&1 else nums2.pop() for x in str(num)])))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestInteger(self, num: int) -> int:\n",
    "        s = str(num)\n",
    "        n = len(s)\n",
    "        g = [[], []]\n",
    "        for i in range(n):\n",
    "            g[int(s[i]) & 1].append(i)\n",
    "        for i in range(2):\n",
    "            g[i].sort(key=lambda i:s[i])\n",
    "        ret = ''\n",
    "        for i in range(n):\n",
    "            ret += s[g[int(s[i]) & 1].pop()]\n",
    "        return int(ret)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestInteger(self, num: int) -> int:\n",
    "        num = list(map(int, str(num)))\n",
    "        l, r = 0, 0\n",
    "        while l < len(num):\n",
    "            r = l + 1\n",
    "            while r < len(num):\n",
    "                if num[l] % 2 == num[r] % 2:\n",
    "                    if num[l] < num[r]:\n",
    "                        num[l], num[r] = num[r], num[l]\n",
    "                r += 1\n",
    "            l += 1\n",
    "        res = 0\n",
    "        for i in num:\n",
    "            res = res*10+i\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestInteger(self, num: int) -> int:\n",
    "        s=str(num)\n",
    "        res, a, b = 0, 0, 0\n",
    "        odd, even, map = [], [], []\n",
    "        for c in s:\n",
    "            if int(c)%2 == 1:\n",
    "                odd.append(int(c))\n",
    "                map.append(1)\n",
    "            else:\n",
    "                even.append(int(c))\n",
    "                map.append(0)\n",
    "        odd.sort(reverse = True)\n",
    "        even.sort(reverse = True)\n",
    "        result=0\n",
    "        for m in map:\n",
    "            if m == 1:\n",
    "                result = result*10 + int(odd[0])\n",
    "                del odd[0]\n",
    "            else:\n",
    "                result = result*10 + int(even[0])\n",
    "                del even[0]\n",
    "        return result\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestInteger(self, num: int) -> int:\n",
    "        oddarr = sorted([c for c in str(num) if c in \"13579\"], reverse=True)\n",
    "        evenarr = sorted([c for c in str(num) if c in \"02468\"], reverse=True)\n",
    "        strans = \"\"\n",
    "        i, j = 0, 0\n",
    "        for x in str(num):\n",
    "            if x in \"13579\":\n",
    "                strans += oddarr[i]\n",
    "                i = i + 1\n",
    "            else:\n",
    "                strans += evenarr[j]\n",
    "                j = j + 1\n",
    "        return int(strans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestInteger(self, num: int) -> int:\n",
    "        nums1,nums2=sorted([int(x) for x in str(num) if x in '13579']),sorted([int(x) for x in str(num) if x in '02468'])      \n",
    "        return int(''.join(map(str,[nums1.pop() if int(x)&1 else nums2.pop() for x in str(num)])))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestInteger(self, num: int) -> int:\n",
    "        tmp=[int(i) for i in str(num)]\n",
    "        even=sorted([i for i in tmp if i%2==0])\n",
    "        odd=sorted([i for i in tmp if i%2!=0])\n",
    "        res=\"\"\n",
    "        for i in range(len(tmp)):\n",
    "            if tmp[i]%2==0:\n",
    "                cur=even.pop()\n",
    "            else:\n",
    "                cur=odd.pop()\n",
    "            res+=str(cur)\n",
    "        return int(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestInteger(self, num: int) -> int:\n",
    "        lst = list(str(num))\n",
    "        lst_i, lst_0, lst_1 = [], [], []\n",
    "        for n in lst:\n",
    "            if int(n) % 2 == 0:\n",
    "                lst_i.append(0)\n",
    "                lst_0.append(n)\n",
    "            else:\n",
    "                lst_i.append(1)\n",
    "                lst_1.append(n)\n",
    "        print(lst_i, lst_0, lst_1)\n",
    "        lst_0.sort(reverse=True)\n",
    "        lst_1.sort(reverse=True)\n",
    "        ans = []\n",
    "        m, n = 0, 0\n",
    "        for i in lst_i:\n",
    "            if i == 1:\n",
    "                ans.append(lst_1[m])\n",
    "                m += 1\n",
    "            else:\n",
    "                ans.append(lst_0[n])\n",
    "                n += 1\n",
    "        return int(\"\".join(ans))"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
